package com.shangguigu.hashtable;

import lombok.ToString;

/**
 * @author: ZhouBert
 * @date: 2019/10/16
 * @description: 我的哈希表 根据图片的思路，将泛型数组和链表进行结合；通过哈希函数对应到数组（一般是取模）
 * 对于 T 需要重写 hashcode
 * todo:关于自定义hashCode的技巧		https://www.cnblogs.com/stitchZsx/p/9558843.html
 * TODO:哈希表可以做缓存的！
 */
@ToString
public class MyHashMap<T> {

	/**
	 * 内置泛型数组（初始化）
	 */
	///HashNode<T>[] arr=(HashNode<T>[]) new Object[100];
	MyLinkedList<T>[] arr;
	/**
	 * 数组大小
	 */
	int arrSize;

	public <T> MyHashMap(int arrSize) {
		this.arrSize = arrSize;
		arr = new MyHashMap.MyLinkedList[arrSize];
		for (int i = 0; i < arrSize; i++) {
			arr[i] = new MyHashMap.MyLinkedList();
		}
	}

	public int hashIndex(T entity) {
		int hashCode = entity.hashCode();
		return hashCode % arrSize;
	}

	public void add(T entity) {
		int index = hashIndex(entity);
		if (!arr[index].find(entity)) {
			arr[index].add(entity);
		}
	}

	public boolean find(T entity){
		int index = hashIndex(entity);
		return arr[index].find(entity);
	}

	public boolean del(T entity){
		int index = hashIndex(entity);
		return arr[index].del(entity);
	}


	@ToString
	class MyLinkedList<T> {

		HashNode<T> dummy = new HashNode<>(null, null);
		/**
		 * 头节点
		 */
		HashNode<T> head;
		/**
		 * 尾节点
		 */
		HashNode<T> rare;

		/**
		 * 初始化
		 */
		public MyLinkedList() {
			head = null;
			///dummy.next = head;
			rare = dummy;
		}

		/**
		 * 增加
		 */
		public void add(T entity) {
			if (isEmpty()) {
				head = new HashNode<>(entity, null);
				dummy.next = head;
				rare = head;
			} else {
				rare.next = new HashNode(entity, null);
				rare = rare.next;
			}
		}

		public boolean isEmpty() {
			return head == null;
		}

		/**
		 * 删除节点
		 *
		 * @param entity
		 * @return
		 */
		public boolean del(T entity) {
			if (isEmpty()) {
				return false;
			}
			HashNode<T> temp = head;
			HashNode<T> pre = dummy;
			while (temp != null) {
				if (temp.val.equals(entity)) {
					///当删除节点为尾节点时
					if (temp == rare) {
						rare = pre;
					}
					pre.next = temp.next;
					temp.next = null;
					head=dummy.next;
					return true;
				}
				temp = temp.next;
				pre = pre.next;
			}
			return false;
		}

		/**
		 * 查找实体
		 *
		 * @param entity
		 * @return
		 */
		public boolean find(T entity) {
			if (isEmpty()) {
				return false;
			}
			HashNode<T> temp = head;
			while (temp != null) {
				if (temp.val.equals(entity)) {
					return true;
				}
				temp=temp.next;
			}
			return false;
		}


	}

	@ToString
	class HashNode<T> {
		public T val;
		public HashNode next;

		public HashNode(T val, HashNode next) {
			this.val = val;
			this.next = next;
		}

	}
}


